package algorithms;

/**
 * 归并排序
 * 规模更小子问题
 * 递归
 * 合并
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 3, 1, 8, 9, 6, 5};
        new MergeSort().mergeSort(arr, 0, arr.length - 1);
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public void mergeSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }

    public void merge(int[] arr, int l, int m, int r) {
        int leftSize = m - l + 1;
        int rightSize = r - m;

        //copy arr to left and right
        int[] left = new int[leftSize];
        for (int i = 0, lc = l; i < leftSize; i++, lc++) {
            left[i] = arr[lc];
        }

        int[] right = new int[rightSize];
        for (int i = 0, rc = m+1; i < rightSize; i++, rc++) {
            right[i] = arr[rc];
        }

        int leftIndex = 0;
        int rightIndex = 0;
        int mergeIndex = l;
        while (leftIndex < left.length && rightIndex < right.length) {
            //left <= right
            if (left[leftIndex] <= right[rightIndex]) {
                arr[mergeIndex] = left[leftIndex];
                leftIndex++;
                mergeIndex++;
            } else {
                arr[mergeIndex] = right[rightIndex];
                rightIndex++;
                mergeIndex++;
            }
        }

        if (leftIndex >= left.length) {
            //copy remaining right arr
            for (int i = rightIndex; i < right.length; i++) {
                arr[mergeIndex] = right[rightIndex];
                mergeIndex++;
                rightIndex++;
            }
        }

        if (rightIndex >= right.length) {
            //copy remaining left arr
            for (int i = leftIndex; i < left.length; i++) {
                arr[mergeIndex] = left[leftIndex];
                mergeIndex++;
                leftIndex++;
            }
        }

    }
}
